package com.algorithm.learning.sort;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/18 21:47
 **/
public class 快速排序_1 {

    public static void main(String[] args) {
//        int[] nums = {3, 4, 6, 1, 0, 2, 6, 2};
//        new 快速排序_1().splitNum1(nums);
//        for (int i : nums) {
//            System.out.print(i + " ");
//        }

//        int[] nums = {3, 4, 6, 1, 0, 2, 6, 2};
//        new 快速排序_1().partition(nums);
//        for (int i : nums) {
//            System.out.print(i + " ");
//        }

        int[] nums = {3, 4, 6, 1, 0, 2, 6, 2};
        new 快速排序_1().quickSort(nums);
        for (int i : nums) {
            System.out.print(i + " ");
        }
    }

    /**
     * 我们现在要实现一个功能
     * 假如提供一个无序的数组,基于这个数组的最右边为基值，进行排序，让其数组的左边都是小于等于基值，数组的右边都是大于基值
     * 但是，左右两边的数仍然是无序的
     *
     * 比如数组nums=[3,4,6,1,0,2,6,2]
     * 那么基值就是2，经过排序后的数组就是[ <=2 (左)| > 2 (右)]
     *
     * 想实现这样的结果，步骤如下：
     * 1、先定义一个小于等于左区间lessEqual=-1, 一个最左的当前值index=0
     * 2、如果当前值nums[index] 小于等于 nums[nums.length - 1](也就是基值), 当前值nums[index]与小于区的下一个数交换nums[lessEqual+1], 并且lessEqual++
     * 3、否则，只有index++
     *
     * 要注意此时，数组整体还是无序的，只是做个划分
     * @param arr
     */
    public void splitNum1(int[] arr) {
        int lessEqual = -1;
        int index = 0;
        while (index < arr.length) {
            if (arr[index] <= arr[arr.length - 1]) {
//                swap(arr, lessEqual + 1, index);
//                lessEqual++;
//                index++;
                swap(arr, ++lessEqual, index++);
            } else {
                index++;
            }
        }
    }

    /**
     * 我们再来实现一个功能，还是一样的
     * 假设有一个无序数组，我们要基于这个数组的最右边为基值，进行排序，让其数组的左边都是小于基值，中间的都是等于基值，数组的右边都是大于基值
     * 也就是基于上面的案例，此时数组要分为三层
     *
     * 比如数组nums=[3,4,6,1,0,2,6,2]
     * 那么基值就是2，经过排序后的数组就是[ <2 (左)| == 2(中) |  > 2 (右)]
     *
     * 想实现这样的结果，步骤如下：
     * 1、首先定义一个小于区less = -1, 一个大于区more = nums.length-1
     * 2、当前数index < 基数p，那么小于区的下一个数进行交换，且小于区右扩less++, 当前数下一个index++;
     * 3、当前数index > 基数p，那么当前数index与大于区more的前一个进行交换，此时大于区左扩, more--;
     *     3.1、要注意的是，当前数index是交换过来的，换过来的新值，还没有和基数比较，所以不用动
     * 4、如果index==more时，此时直接交换当前数与最右边的数
     *
     * 按照上面的步骤，我们来看下数组的流程，nums = [3,4,6,1,0,2,6,2]
     * 此时less=-1, more=length-1=7, index=0, p = 2;
     * 1、首先当前数nums[index] = 3, 此时是大于2的，那根据上面的步骤，当前数与大于区more的前一个进行交换，也就是nums[more-1]=6，此时数组为[6,4,6,1,0,2,3,2]，并且more=more-1=6;
     * 2、要注意此时index是没动的，但是nums[index] = 6, 那么再跟p=2进行比较，又是大于2，那么在继续与大于区more的前一个进行交换，也就是nums[more-1] = 2, 此时数组为[2,4,6,1,0,6,3,2], 并且more = more - 1 = 5;
     * 3、此时当前数nums[index] = 2 = p, 此时当前数index直接+1，即index++ = 1,
     * 4、此时当前数nums[index] = 4 > 2, 那么再循环步骤，那么在继续与大于区more的前一个进行交换，也就是nums[more-1] = 0, 此时数组为[2,0,6,1,4,6,3,2], 并且more = more - 1 = 4;
     * 5、要注意此时index是没动的，但是nums[index] = 0 > 2, 当前数index < 基数p，那么小于区less的下一个数进行交换，此时less=-1，那么less的下一个数就是nums[less+1] = 2, 进行交换后的数组为[0,2,6,1,4,6,3,2]，less+1==0,index+1=2;
     * 6、当前数nums[index] = 6 > 2, 再循环步骤，继续与大于区more的前一个进行交换，也就是nums[more-1]=6, 此时数组[0,2,1,6,4,6,3,2]，并且more = more - 1 = 3;
     * 7、此时nums[index] = 1 < 2 那么那么小于区less的下一个数进行交换，此时less=0, 那么less的下一个数就是nums[less+1] = 2，那么也就是nums[less+1] = nums[index], 最后的数组就是[0,1,2,6,4,6,3,2]
     * 8、此时index == more, 此时只需要将大于区数与基数进行交换即可，也就是nums[more] = nums[length - 1]，而此时more=3, 那么nums[more] = 6， 最后的数组就是[0,1,2,2,4,6,3,6]
     *
     * @param arr
     */
    public void splitNum2(int[] arr) {
        int less = -1;
        int more = arr.length - 1;
        int index = 0;
        while (index < more) {
            if (arr[index] < arr[arr.length - 1]) {
                swap(arr, ++less, index++);
            } else if (arr[index] == arr[arr.length - 1]) {
                index++;
            } else {
                swap(arr, index, --more);
            }
        }
        swap(arr, more, arr.length - 1);
    }

    /**
     * 根据splitNum2方法的流程，我们把左右区域的边界进行抽象，
     * 原来左边界就是 0, 现在改为L，右边界是arr.length - 1, 现在改为R
     * 最后返回当前中间等于区域的下标范围。
     *
     * 我们还是以nums = [3,4,6,1,0,2,6,2]为例：
     *
     * 我们知道根据上面的步骤进行排序后，整个数组被分为三部分[ < 2 | == 2 | > 2]，即[0,1,2,2,4,6,3,6]
     * 也就是说，其实2这个值就是在当前数组的一个有序位置了，因为左边的都小于2，右边的都大于2，
     * 所以此时，我们只需要在对等于区域的左右边进行排序，那么最后整个的数组就是有序的！！！
     *
     * 那么很明显我们可以通过递归来进行排序。
     * 所以我们需要返回上次排序后，等于区域的下标范围，再根据其下标范围，再来划分下一次递归的左右区域即可
     *
     * @param arr
     * @param left
     * @param right
     */
    public int[] partition(int[] arr, int left, int right) {
        // 左区域起始位置
        int less = left - 1;
        // 右区域起始位置
        int more = right;
        // index就是当前数
        int index = left;
        while (index < more) {
            if (arr[index] < arr[right]) {
                // 如果当前数小于 右边的基数，那么左区域向右移，当前值index向右移一位，并且当前值与左区域的下一个位数进行交换
                swap(arr, ++less, index++);
            } else if (arr[index] == arr[right]) {
                //  如果当前数 等于 右边的基数，那么当前值index向右移一位即可
                index++;
            } else {
                //  如果当前数 大于 右边的基数，那么当前数与右区域的下一位数进行交换，并且右区域左移
                swap(arr, index, --more);
            }
        }
        // 最后如果当前值与右区域重叠了，那么直接把当前值与基值进行交换
        swap(arr, index, right);
        // 返回当前中间等于区域的下标范围
        return new int[] {less + 1, more};
    }

    public void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // 返回等于区域
        int[] equalArea = partition(arr, L, R);
        // equalArea[0]是等于区域的第一个数
        // equalArea[1]是等于区域的最后一个数
        process(arr, L, equalArea[0] - 1);
        process(arr, equalArea[1] + 1, R);
    }

    /**
     * 快速排序-递归版本
     * @param arr
     */
    public void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }


    public void swap(int[] arr, int old, int n) {
        int temp = arr[old];
        arr[old] = arr[n];
        arr[n] = temp;
    }

}
